Syllabus Information

1.1. Introduction

In the Mathematics degree of University of Zaragoza, "Graphs and Combinatorics" is a compulsory subject taught in the first year. It is included in the module Discrete Mathematics and Optimization, and is devoted essentially to the study of discrete structures. The two main topics of the subject are Combinatorics and Graph Theory. Special emphasis is placed on problem solving.

4.1. Assessment tasks (description of tasks, marking system and assessment criteria)

Grading.

For regular students two options:

a)     - Homework (Completion of four problem sets)  --- 20%  of the score.

        - Final exam                                                     --- 80%  of the score.

b)     Only final exam (100%)

For non-regular students only option b).

5.1. Methodological overview

This course covers elementary discrete mathematics. It emphasizes mathematical definitions and proofs as well as applicable methods
The course consists of lectures and solving problem classes on the topics:  "permutations and combinations", "counting principles",  "recurrences", "generating functions", "elementary graph theory", "shortest path problems" and "optimal flow problems".

Four problem sets will be assigned during the course. Material covered in exercises will be tested on exams.

5.2. Learning tasks

The course consists of  lectures ( 2 sessions / week, 1 hour / session, 30 sessions) and solving problem classes (2 sessions / week, 1 hour / session, 30 sessions).

There are 4 problem sets. Typically, a problem set is due two week after it is assigned. By solving the problem sets a student can get 20% of the final score.

There are 4 additionals sessions  devoted to solving questions related with the homework. For these additional sesssions the students are splitted into small groups.

The students  can attend office hours and send questions to him/her teacher via email.

Additional information on the subject (calendar, timetable, problem sets, lecture notes,...)  appears in the web page of the subject (in University of Zaragoza ADD, https://moodle2.unizar.es/add/course/view.php?id=StudentCode).

5.3. Syllabus

Program of the subject:

Part I

1.- Enumerative Combinatorics: Permutations and Combinations.

2.- Binomial coefficients and binomial formula.

3.- Recurrence relations. Some applications.

4.- The inclusion-exclusion principle. Applications.

Part II

5.- Generating Functions.

6.- Rational Generating Functions.

Part III

7.- Graphs: Definitions and notation.  

8.- Traversing a Graph. Algorithms  BFS and DFS.

9.- Applications of Graph Traversal: Connected components, strong components, bases.

10.-The number of trees and paths of a graph.

Part IV

11.- Weighted Graphs. Algorithms for the minimum spanning tree problem.

12.- The shortest path problem. Dijkstra’s algorithm.

13.- PERT-CPM algorithms for scheduling a set of project activities.

Part V

14.- Maximum flow in a network.

15.- The Ford- Fulkerson method for calculating a maximum flow.

16.- Menger’s theorems on connectivity of graphs.

17.- Maximum matching in bipartite graphs. Hall’s theorem.

18.- Some NP-Hard problems on graphs.

5.5. Bibliography and recommended resources

Bibliography.

Main:

Lecture notes of the subject at https://moodle2.unizar.es/add/course/view.php?id=8357

Complementary books: